Redis入门：数据分片算法

hash取余对数据key-value的key值做hash取余计算，得到结果只要key值不变(字符串相等)取余结果在[0,1,2,3,…,n-1]，n=分片个数(节点个数)。 计算公式如下：

结论1：当key值不变时，可以得到一个不变的正整数。

结论2：当key值不变时，可以通过hash取余得到[0,1,2,…,N-1]一个不变的取余结果。

hash取余就可以应用在redis分布式数据分片计算逻辑中。

当有key-value出现时，先对key做hash取余n是节点个数(现在是3)；所有节点jedis排序(list) 0 1 2 … n-1 使用到取余结果对应到一个固定的jedis对象，最终连接固定的redis节点。

在一个频繁发生扩容缩容的分布式结构中，hash取余不适用，但是N不发生变化的结构中总是使用hash取余。

作为散列算法，考虑分布式缓存中的数据分片过程的哈希取余的缺点。

数据倾斜：

例如：3个redis节点，在散列计算后的存储数据有可能是以下情况：

此情况已经产生了2500条数据的最大偏移，按此比例计算，当数据存储量上亿条时，这种数据倾斜会造成集群中节点间巨大的负载差距。

解决数据倾斜的方法：

哈希取余的散列计算，在增加或者减少节点的时候，会导致数据迁移量过大。

由上述原因，jedis的数据分片没有使用hash取余计算而是引入的hash一致性。

1997年麻省理工学院的学生开发了哈希一致性的计算方法。引入了一个0-43亿的整数哈希环(0-2^32)，把节点的ip和端口和其他信息作为字符串的对象进行散列计算。

例如："192.168.40.120:6379^

jedis对将要存储的key做同样的散列计算。

例如："ITEM_CAT_0"--散列计算--[0-2^32]的整数。

利用这个hash环上的对应内容的散列结果，对key做顺时针寻找最近节点映射整数的判断，以这样一种计算，将所有的key值进行数据分片的计算。

如下图所示：

当增加节点node4时，如下图：

对于当前存在的数据，只需要根据顺时针最近节点的计算原理，迁移key4，其他的key都不用动。按此来说，只要迁移绿色线条上的数据即可。

当节点删除时(node3)，如下图：

对于当前存在的数据，只需要迁移key2和key3到node2即可。如果数据较多，只需迁移node3的数据到node2即可，也就是蓝色线条上的所有数据。

单独的使用节点ip+端口+其他信息的散列映射，有可能导致数据的倾斜量过大。为了解决数据平衡的问题，hash一致性引入虚拟节点的概念。

针对虚拟节点的官方说明，每个物理节点默认会产生1000个虚拟节点，散列分布在hash环上，就相当于每个物理节点分割成了1001个节点，这样多节点的散列分布就能保证数据的平衡存储。如下图：

在没有虚拟节点的情况下，node2需要存储key2、key3、key4、key5，node1存储key1，数据就产生了较大的倾斜。

当引入了虚拟节点的映射(ip+端口+#1)，虚拟节点大致算法如下：

此时key值存放结果变成node1存储key1、key2、key4，node2存储key3、key5。数据存储就相对平均了。